package leetcode.primary;

import java.util.*;
/*
 */
public class T15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        ArrayList<Triplet> a = new ArrayList<Triplet>();
        quicksort(nums,0,len-1);

        int zero = 0;
        int i,j;

        for( i=0;i<len;i++){
            if(nums[i]>=0){
                break;
            }
        }
        zero = i;

        for(i=0;i<=zero;i++){              //找a+b<=0的组合
            for(j=i+1;j<len && nums[j]<= -nums[i];j++){
                if(judge(a,nums[i],nums[j])){
                    Triplet tp = new Triplet();
                    tp.setFt(nums[i]);
                    //System.out.print(tp.ft+"  ");
                    tp.setSd(nums[j]);
                    //System.out.println(tp.sd);
                    tp.setSum1_2();
                    tp.flag = j;
                    a.add(tp);
                }

            }
        }
        for(j=0;j<a.size();j++){
            for(i=zero;i<len;i++) {
                if (a.get(j).sum1_2 + nums[i] == 0 && i>a.get(j).flag) {
                    a.get(j).td = nums[i];
                }
            }
        }

        List<List<Integer>> ls = new ArrayList<List<Integer>>();
        for(i=0;i<a.size();i++){
            if(a.get(i).td!=(-1)){
                ArrayList<Integer> al = new ArrayList<Integer>();
                al.add(a.get(i).ft);
                System.out.print(a.get(i).ft+"  ");
                al.add(a.get(i).sd);
                System.out.print(a.get(i).sd+"  ");
                al.add(a.get(i).td);
                System.out.println(a.get(i).td);
                ls.add(al);
            }
        }
        return ls;
    }
    void quicksort(int[] a,int left, int right) {
        int i, j, t, temp;
        if(left > right)
            return;
        temp = a[left];    //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要，要先从右边开始找
            while(a[j] >= temp && i < j)
                j--;
            while(a[i] <= temp && i < j)//再找右边的
                i++;
            if(i < j)//交换两个数在数组中的位置
            {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(a,left, i-1);//继续处理左边的，这里是一个递归的过程
        quicksort(a,i+1, right);//继续处理右边的 ，这里是一个递归的过程
    }

    boolean judge(ArrayList<Triplet> a,int x,int y){
        if(a.size()==0){
            return true;
        }
        for(int i=0;i<a.size();i++){
            if(a.get(i).ft==x && a.get(i).sd==y){
                return false;
            }
        }
        return true;
    }
    public static  void main(String[] args){
        T15 cc = new T15();
        int[] nums = {0,0,0};
        List<List<Integer>> ccc = cc.threeSum(nums);
    }

}

class Triplet{
    int ft;
    int sd;
    int td=-1;
    int sum1_2;
    int flag;
    void setFt(int ft){
        this.ft = ft;
    }
    void setSd(int sd){
        this.sd = sd;
    }
    void setTd(int td){
        this.td = td;
    }
    void setSum1_2(){
        this.sum1_2 = this.ft + this.sd;
    }
}
